package arrAndstr;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
    138. 随机链表的复制
 */
public class T138 {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static void main(String[] args) {

    }

    public static Node copyRandomList(Node head) {
        if (head == null)   return head;

        Map<Node, Node> map = new HashMap<>();
        Node tempHead = head;
        Node node = new Node(tempHead.val);
        map.put(tempHead, node);
        Node result = node;

        // val
        while (tempHead.next != null) {
            tempHead = tempHead.next;
            node.next = new Node(tempHead.val);
            node = node.next;
            map.put(tempHead, node);
        }

        // random
        tempHead = head;
        node = result;
        System.out.println(tempHead.random == null);
        node.random = tempHead.random == null ? null : map.get(tempHead.random);
        while (tempHead.next != null) {
            tempHead = tempHead.next;
            node = node.next;
            node.random = tempHead.random == null ? null : map.get(tempHead.random);
        }

        return result;
    }
}
